package com.example.search;

public class FibonacciSearch {
    // 生成斐波那契数列直到大于等于数组长度的数
    public static int[] createFibonacci(int maxSize) {
        int[] fib = new int[maxSize + 1];
        fib[0] = 0;
        fib[1] = 1;
        for (int i = 2; i <= maxSize; i++) {
            fib[i] = fib[i - 1] + fib[i - 2];
        }
        return fib;
    }

    public static int fibonacciSearch(int[] arr, int key) {
        int low = 0;
        int high = arr.length - 1;
        int k = 0; // 表示斐波那契分割点在数组中的位置
        int fib[] = createFibonacci(high + 1); // 生成斐波那契数列

        // 寻找斐波那契数列中大于等于数组长度的最小斐波那契数的索引
        while (fib[k] < arr.length) {
            k++;
        }

        // 扩展数组，使数组的长度为斐波那契数，用最后一个元素填充扩展部分
        int[] temp = new int[fib[k]];
        System.arraycopy(arr, 0, temp, 0, arr.length);
        for (int i = arr.length; i < temp.length; i++) {
            temp[i] = arr[arr.length - 1];
        }

        while (low <= high) {
            // 确定分割点
            int mid = low + fib[k - 1] - 1;

            if (mid >= temp.length) {
                return -1; // 如果计算出的 mid 超出扩展数组的范围，返回 -1
            }

            if (key < temp[mid]) {
                high = mid - 1;
                k--;
            } else if (key > temp[mid]) {
                low = mid + 1;
                k -= 2;
            } else {
                // 找到元素，判断是否在原数组范围内
                if (mid < arr.length) {
                    return mid;
                } else {
                    // 如果是在扩展部分找到的，返回原数组的最后一个元素的索引
                    return arr.length - 1;
                }
            }
        }
        return -1; // 查找失败
    }

    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19};
        int key = 11;
        int index = fibonacciSearch(arr, key);
        if (index != -1) {
            System.out.println("元素 " + key + " 在数组中的位置为：" + index);
        } else {
            System.out.println("元素 " + key + " 不在数组中");
        }
    }
}